\chapter{Specification of Derived Instances}  \label{derived} \index{instance!derived}

A \emph{derived instance} is an instance that results from a \hyperref[derivedcl]{\texttt{derive} declaration}.
The body of a derived instance is derived syntactically from the definition of the associated type. Derived instances are possible only for certain classes known to the compiler.

\section{Derived Instances for Eq}

Instances of \texttt{Eq} are types whose values can be compared for equality. \texttt{Eq} instances can be derived for all algebraic data types.

\trans{
Let $P$ be a $n$-ary $(n \ge 0)$ type constructor for a product type with $k$-ary $(k \ge 0)$ data constructor $C$:
\begin{flushleft}
\textbf{data} $P$ $u_1$ $\cdots$ $u_n$ = $C$ $ct_1$ $\cdots$ $ct_k$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Eq} ($P$ $t_1$ $\cdots$ $t_n$)\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Eq}  ($Eq$ $t_1$, $\cdots$, $Eq$ $t_n$) \sym{=>} ($P$ $t_1$ $\cdots$ $t_n$) \textbf{where}\\
\hspace{0.3cm}$C$ $a_1$ $\cdots$ $a_k$ \texttt{==} $C$ $b_1$ $\cdots$ $b_k$ \texttt{=}\\
\hspace{0.6cm}\textbf{true} \texttt{\&\&} $a_1$\texttt{.==} $b_1$ \texttt{\&\&} $\cdots$ \texttt{\&\&} $a_k$\texttt{.==} $b_k$\\
\hspace{0.3cm}hashCode $x$ \texttt{=} $\cdots$\\
\end{flushleft}
}

The generated expression for the \sym{==} operator returns \textbf{true} if all subcomponents of the left operand are pairwise equal with the corresponding subcomponents of the right operand, otherwise the result is  \textbf{false}.

Note that the special case $k=0$ is trivial: such a type has only one value $C$ and the derived \texttt{==} returns always \textbf{true}.

The generated expression for \term{hashCode} computes a value of type \term{Int} suitable for use in hash tables and similar data structures. In the process of doing so, all sub-components of the value will be evaluated recursively. The result is undefined for infinite values.


The case gets only marginally more complex with sum types.
\trans{
Let $S$ be a $n$-ary $(n \ge 0)$ type constructor for a sum type with $m$  $(m \ge 2)$ data constructors $C_1, \cdots, C_m$ and arities $k_1, \cdots, k_m$:
\begin{flushleft}
\textbf{data} $S$ $u_1$ $\cdots$ $u_n$ = $C_1$ $ct_{1_1}$ $\cdots$ $ct_{k_1}$ $| \cdots |$ $C_m$ $ct_{m_1}$ $\cdots$ $ct_{k_m}$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Eq} ($S$ $t_1$ $\cdots$ $t_n$)\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Eq} ($Eq$ $t_1$, $\cdots$, $Eq$ $t_n$) \sym{=>} ($S$ $t_1$ $\cdots$ $t_n$) \textbf{where}\\
\hspace{0.33cm}$a$ \texttt{==} $b$ \texttt{=} \textbf{case} $(a, b)$ \textbf{of}\\
\hspace{0.66cm}$(C_1 a_1 \cdots a_{k_1}, C_1 b_1 \cdots b_{k_1})$\\
\hspace{2cm}$\rightarrow$ \textbf{true}  \texttt{\&\&} $a_1$\texttt{.==} $b_1$ \texttt{\&\&} $\cdots$ \texttt{\&\&} $a_{k_1}$\texttt{.==} $b_{k_1}$\\
\hspace{0.66cm}$\cdots$\\
\hspace{0.66cm}$(C_m a_1 \cdots a_{k_m}, C_m b_1 \cdots b_{k_m})$\\
\hspace{2cm}$\rightarrow$ \textbf{true} \texttt{\&\&} $a_1$\texttt{.==} $b_1$ \texttt{\&\&} $\cdots$ \texttt{\&\&} $a_{k_m}$\texttt{.==} $b_{k_m}$\\
\hspace{0.66cm}\_ $\rightarrow$ \textbf{false}\\
\hspace{0.3cm}hashCode $x$ \texttt{=} $\cdots$\\
\end{flushleft}
}

The expression $a$ \texttt{==} $b$ evaluates to \textbf{true} if both $a$ and $b$ were constructed with the same data constructor and their corresponding subcomponents are pairwise equal.

\subsubsection{Derived Instances for Ord}
The \texttt{Ord} class is used for totally ordered datatypes. It is a subclass of \texttt{Eq} and inherits the operations \texttt{==} and \texttt{!=}. It defines one new operation \texttt{<=>} that must be implemented by all instances, and operations \texttt{<}, \texttt{<=}, \texttt{>}, \texttt{>=}, \texttt{max} and \texttt{min} in terms of \texttt{<=>}.

The compare function \texttt{<=>}
\footnote{The alias \texttt{compare} is provided  for \haskell{} compatibility.}
compares two values and returns a result of type \texttt{Ordering}, which is defined as
\footnote{Aliases \texttt{LT},  \texttt{EQ} and \texttt{GT} are provided for \haskell{} compatibility.}
\begin{code}
    data Ordering = Lt | Eq | Gt
\end{code}

Instances of \texttt{Ord} can be derived for all algebraic data types that are either already instances of \texttt{Eq} or have an implementation for \texttt{hashCode}.

The translation shown here does not handle the case of the trivial product type. Such a type will have an implementation of \texttt{<=>} that always returns \texttt{Ordering.Eq}.

For product types, the generated expression compares the components $a_i$, $b_i$ from 1 to $k-1$; the first result $r_i$ that does not signify equality is the result of the overall comparison. Otherwise, if all component pairs up to ${k-1}$ compare equal, the result is the ordering of the last component pair, $a_k$\texttt{.<=>} $b_k$.


\trans{
Let $P$ be a $n$-ary $(n \ge 0)$ type constructor for a product type with $k$-ary $(k \ge 1)$ data constructor $C$:
\begin{flushleft}
\textbf{data} $P$ $u_1$ $\cdots$ $u_n$ = $C$ $ct_1$ $\cdots$ $ct_k$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Ord} ($P$ $t_1$ $\cdots$ $t_n$)\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Ord} ($Ord$ $t_1$, $\cdots$, $Ord$ $t_n$) \sym{=>} ($P$ $t_1$ $\cdots$ $t_n$) \textbf{where}\\
\hspace{0.33cm}$(C a_1 \cdots a_k)$ \texttt{<=>} $(C b_1 \cdots b_k)$ \texttt{=} \textbf{case} $a_1$\texttt{.<=>} $b_1$ \textbf{of}\\
\hspace{0.66cm}\texttt{Eq} $\rightarrow$\\
\hspace{1cm}$\cdots$\\
\hspace{1.33cm}\textbf{case} $a_{k-1}$\texttt{.<=>} $a_{k-1}$ \textbf{of}\\
\hspace{1.66cm}\texttt{Eq} $\rightarrow$ $a_k$\texttt{.<=>} $b_k$\\
\hspace{1.66cm}$r_{k-1}$ $\rightarrow$ $r_{k-1}$\\
\hspace{1cm}$\cdots$\\
\hspace{0.66cm}$r_1$ $\rightarrow$ $r_1$\\
\end{flushleft}
}

Derived instances for sum types make use of the Prelude function
\begin{quote}
\texttt{constructor} :: $any \rightarrow$ \texttt{Int}
\end{quote}
which returns the index of the constructor for algebraic data types.\footnote{The constructors are numbered starting from 0 in the order they appear in the \hyperref[algdcl]{data declaration}.}

The code for sum types first sorts out the cases where the constructors are not the same; the result in such a case is the ordering of the constructors. The remaining $m$ cases compare nullary constructors equal to themselves, values with unary constructors compare just like the components compare and values with constructors of higher arity compare like the tuples constructed from their components would compare when $k_i$-ary tuples had a derived instance of \texttt{Ord}.

\trans{
Let $S$ be a $n$-ary $(n \ge 0)$ type constructor for a sum type with $m$  $(m \ge 2)$ data constructors $C_1, \cdots, C_m$ and arities $k_1, \cdots, k_m$:
\begin{flushleft}
\textbf{data} $S$ $u_1$ $\cdots$ $u_n$ = $C_1$ $ct_{1_1}$ $\cdots$ $ct_{k_1}$ $| \cdots |$ $C_m$ $ct_{m_1}$ $\cdots$ $ct_{k_m}$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Ord} ($S$ $t_1$ $\cdots$ $t_n$)\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Ord} ($Ord$ $t_1$, $\cdots$, $Ord$ $t_n$) \sym{=>} ($S$ $t_1$ $\cdots$ $t_n$) \textbf{where}\\
\hspace{0.33cm}$a$ \texttt{<=>} $b$ \texttt{=} \textbf{case} $($\texttt{constructor} $a)$\texttt{<=>} $($\texttt{constructor} $b)$ \textbf{of}\\
\hspace{0.66cm}\texttt{Eq} $\rightarrow$ \textbf{case} $(a,b)$ \textbf{of}\\
\hspace{1cm}$alt_1$\\
\hspace{1cm}$\cdots$\\
\hspace{1cm}$alt_m$\\
\hspace{0.66cm}$r_0$ $\rightarrow$ $r_0$
\end{flushleft}
where each of the alternatives $alt_i$ has a form that depends on the arity of the constructor $C_i$:
\begin{flushleft}
\hspace{0.3cm}$(C_i, C_i) \rightarrow$ \texttt{Eq}\hspace{\fill}for nullary $C_i$\\
\hspace{0.3cm}$(C_i a_1, C_i b_1) \rightarrow a_1$\texttt{.<=>} $b_1$ \hspace{\fill}for unary $C_i$\\
\hspace{0.3cm}$(C_i a_1 \cdots a_{k_i}, C_i b_1 \cdots b_{k_i}) \rightarrow$ \hspace{\fill}for $C_i$ with arity $k_i \ge 2$\\
\hspace{1cm}$(a_1, \cdots, a_{k_i})$\texttt{.<=>} $(b_1, \cdots, b_{k_i})$
\end{flushleft}
}

\section{Derived Instances for Enum}

The \texttt{Enum} class can be derived for algebraic datatypes that have only nullary constructors.
It provides conversion from and to \texttt{Int} values, successor and predecessor functions and the operations \emph{enumFrom}, \emph{enumFromTo}, \emph{enumFromThen} and \emph{enumFromThenTo} to construct \hyperref[aseq]{arithmetic sequences}. \texttt{Enum} is a subclass of \texttt{Ord} and hence of \texttt{Eq}.

In addition to the above, derived instances also provide the operation \emph{hashCode} required for instances of \texttt{Eq}. In derived instances, \emph{hashCode} is always the same as \emph{ord} and not shown in the translations.

In all derived instances, the following holds for the successor and predecessor functions:

\trans{
\begin{flushleft}
\hspace{0.5cm}succ e = from (ord e + 1)\\
\hspace{0.5cm}pred e = from (ord e - 1)\\
\end{flushleft}
}
This implies that the successor of the last enumeration value as well as the predecessor of the first enumeration value are undefined.

\hasdiff{The functions \emph{toEnum} and \emph{fromEnum} are know as \emph{from} and \emph{ord} in \frege{}. Aliases are provided for compatibility.}

A trivial type can be an instance of \texttt{Enum}.
\trans{
Let $T$ be a trivial type:
\begin{flushleft}
\textbf{data} $T$ = $C$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Enum} $T$\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Enum} $T$ \textbf{where}\\
\hspace{0.5cm}ord $C$ = 0; from 0  = $C$; succ \_ = undefined; pred \_ = undefined;\\
\hspace{0.5cm}enumFrom \_ = [$C$]; enumFromTo \_ \_ = [$C$];\\ 
\hspace{0.5cm}enumFromThen \_ \_ = [$C$]; enumFromThenTo \_ \_ \_ = [$C$]; 
\end{flushleft}
}
Note that predecessor and successor are undefined, and all arithmetic sequences result in a list with just one element, $C$.

Product types with arity $k>0$ cannot be derived instances of \texttt{Enum}. It remains to show the translation for those sum types that can be instances of \texttt{Enum}.

\trans{
Let $S$ be a sum type with $m$ $(m \ge 2)$ nullary constructors $C_1$, $\cdots$, $C_{m-1}$:
\begin{flushleft}
\textbf{data} $S$ = $C_1 | \cdots | C_m$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Enum} $S$\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Enum} $S$ \textbf{where}\\
\hspace{0.5cm}ord $e$ = \textbf{case} $e$ \textbf{of}\\
\hspace{1.0cm}$C_1 \rightarrow$ 0\\
\hspace{1.0cm}$\cdots$\\
\hspace{1.0cm}$C_m \rightarrow$ $m-1$\\
\hspace{0.5cm}from $i$  = \textbf{case} $i$ \textbf{of}\\
\hspace{1.0cm}0 $\rightarrow C_1$\\
\hspace{1.0cm}$\cdots$\\
\hspace{1.0cm}$m-1$ $\rightarrow C_m$\\
\hspace{0.5cm}enumFromTo $a$ $b$ = \textbf{if} $a \le{} b$ \textbf{then} $a$:enumFromTo $($succ $a)$ $b$ \textbf{else} \bracka{}\brackz{}\\
\hspace{0.5cm}enumFrom $a$ = enumFromTo $a$ $C_m$\\
\hspace{0.5cm}enumFromThen $a$ $b$ = enumFromThenTo $a$ $b$ (\textbf{if} $a \le{} b$ \textbf{then} $C_m$ \textbf{else} $C_1$)\\
\hspace{0.5cm}enumFromThenTo $a$ $b$ $c$ = map from \\
\hspace{3.5cm}(Int.enumFromThenTo (ord $a$) (ord $b$) (ord $c$))\\
\end{flushleft}
}
Note that the construct $m-1$ will be substituted by the appropriate integer constant. The application ($S$\texttt{.from} $i$) is undefined for $(i<0)$ or $(i \ge m)$. For all $C_i$ it is the case that $S$\texttt{.from} $C_i$\texttt{.ord ==} $C_i$

\section{Derived instances for Bounded}

This type class defines two per type constants \emph{minBound} and \emph{maxBound} and can be derived for enumeration types.
\trans{
Let $S$ be a sum type with $m$ $(m \ge 2)$ nullary constructors:
\begin{flushleft}
\textbf{data} $S$ = $C_1 | \cdots | C_m$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Bounded} $S$\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Bounded} $S$ \textbf{where}\\
\hspace{0.5cm}minBound = $C_1$\\
\hspace{0.5cm}maxBound = $C_m$\\
\end{flushleft}
}

\section{Derived instances for Show}

The type class \texttt{Show} is for types whose values can be represented as character strings. It can be derived for any algebraic data type.

\trans{
Let $S$ be a $n$-ary $(n \ge 0)$ type constructor for a type with $m$  $(m \ge 1)$ data constructors $C_1, \cdots, C_m$ and arities $k_1, \cdots, k_m$:
\begin{flushleft}
\textbf{data} $S$ $u_1$ $\cdots$ $u_n$ = $C_1$ $ct_{1_1}$ $\cdots$ $ct_{k_1}$ $| \cdots |$ $C_m$ $ct_{m_1}$ $\cdots$ $ct_{k_m}$\\
\hspace{1cm}Then\\
\textbf{derive} \texttt{Show} ($S$ $t_1$ $\cdots$ $t_n$)\\
\hspace{1cm}is equivalent to:\\
\textbf{instance} \texttt{Show} ($Show$ $t_1$, $\cdots$, $Show$ $t_n$) \sym{=>} ($S$ $t_1$ $\cdots$ $t_n$) \textbf{where}\\
\hspace{0.5cm}\texttt{show v =} \textbf{case} \texttt{v} \textbf{of}\\
\hspace{1cm}$C_1 a_1 \cdots a_{k_1} \rightarrow$ \texttt{"}$C_i$\texttt{" ++ " "}\\
\hspace{2cm}\texttt{ ++} $a_1$\texttt{.showsub ++} $\cdots$ \texttt{" " ++} $a_k$ \texttt{.showsub}\\
\hspace{1cm}$\cdots$\\
\hspace{1cm}$C_m a_1 \cdots a_{k_m} \rightarrow \cdots$\\
\hspace{0.5cm}\texttt{showsub} $C_i$ \texttt{=} \texttt{"}$C_i$\texttt{"}\hspace{\fill}for each $i$ where $k_i=0$\\
\hspace{0.5cm}\texttt{showsub} $C_i a_1 \cdots a_{k_i}$ \texttt{=} \hspace{\fill}for each $i$ where $k_i>0$\\
\hspace{2cm}\texttt{"(" ++ show (} $C_i a_1 \cdots a_{k_i}$\texttt{) ++ ")"}
\end{flushleft}
}

The derived \texttt{show} functions create a textual representation of a value that will be syntactically reminiscent of a  constructor application if the \texttt{Show} instances of the subcomponents behave likewise. The \texttt{showsub} function shows the value enclosed in parenthesis if it is more complex than just a nullary constructor.

The translation above is equally valid for product and sum types. Types that enjoy special syntactic support (list types, tuples,  and the unit type) have also special \texttt{Show} instances whose translation is omitted for brevity. Suffice it to say that these instances will reproduce the familiar textual representations, i.e. the expression \texttt{show (1,2)} will produce \texttt{"(1, 2)"} and not \texttt{"(,) 1 2"}.
